package com.LeeCode;

import java.util.*;

/**
 * 找出最安全路径
 */

public class Code2812 {
    public static void main(String[] args) {
        List<List<Integer>> grid = new ArrayList<>();

        // 添加第一行
        grid.add(Arrays.asList(0, 0, 1));

        // 添加第二行
        grid.add(Arrays.asList(0, 0, 0));

        // 添加第三行
        grid.add(Arrays.asList(0, 0, 0));

        System.out.println(new Code2812().maximumSafenessFactor(grid));

    }

    public int maximumSafenessFactor(List<List<Integer>> grid) {
        int n = grid.size(), m = grid.get(0).size();
        if (grid.get(0).get(0) == 1 || grid.get(n - 1).get(m - 1) == 1) return 0;
        List<Integer> thief = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid.get(i).get(j) == 1) {
                    thief.add(i * m + j);
                }
            }
        }
        int left = 0, right = m + n - 1;
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            if (check(n, m, thief, mid))
                left = mid;
            else
                right = mid;
        }
        return left;
    }

    private boolean check(int n, int m, List<Integer> thief, int save) {
        int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        boolean[][] visited = new boolean[n][m];
        Queue<Integer> queue = new LinkedList<>();

        if (visible(0, 0, thief, m, save)) {
            queue.add(0);
            visited[0][0] = true;
        }
        while (!queue.isEmpty()) {
            int cur = queue.poll();
            int x = cur / m, y = cur % m;
            for (int[] direction : directions) {
                int nx = x + direction[0], ny = y + direction[1];
                if (nx >= 0 && nx < n && ny >= 0 && ny < m && !visited[nx][ny]) {
                    if (visible(nx, ny, thief, m, save)) {
                        queue.add(nx * m + ny);
                        visited[nx][ny] = true;
                    }
                }
            }
        }

        return visited[n - 1][m - 1];
    }

    private boolean visible(int row, int col, List<Integer> thief, int m, int save) {
        int dist = Integer.MAX_VALUE;
        for (Integer i : thief) {
            int x = i / m, y = i % m;
            dist = Math.min(dist, Math.abs(row - x) + Math.abs(col - y));
        }
        return dist >= save;
    }
}
